package Hot_100;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

//合并区间
//和hot100函数结构对应，会报数组越界异常
public class Hot_100_56 {
    /**
     * 主函数
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        //输入数组行数，列固定为两列
        int m=sc.nextInt();
        //初始化二维数组
        int arr[][]=new int[m][2];
        for(int i=0;i<m;i++){
            for(int j=0;j<2;j++){
                arr[i][j]=sc.nextInt();
            }
        }
        //调用处理函数
        arr=merge(arr);
        //输出结果
        for(int i=0;i<m;i++){
            for(int j=0;j<2;j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }

    /**
     * 合并区间
     * @param intervals
     * @return
     */
    public static int[][] merge(int[][] intervals) {
        LinkedList<int[]> ans=new LinkedList<>();
        //按各一维数组起点升序排列
        Arrays.sort(intervals,(a, b)->{
            return a[0]-b[0];
        });
        //把第一组数添加到ans
        ans.add(intervals[0]);
        for(int i=1;i<intervals.length;i++){
            //依次取出intervals后面的每组数
            int cur[]=intervals[i];
            //获取ans最后一组数的引用
            int last[]=ans.getLast();
            if(cur[0]<=last[1]){
                //合并
                last[1]=Math.max(cur[1],last[1]);
            }else{
                //处理下一个待合并的区间
                ans.add(cur);
            }
        }
        return ans.toArray(new int[0][0]);
    }
}
//时间复杂度: O(n)
//空间复杂度: O(n)